#include <iostream>

using namespace std;
// 242. 有效的字母异位词
// 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
// 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
// s 和 t 仅包含小写字母
// 输入: s = "anagram", t = "nagaram"
// 输出: true

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size())
            return false;
        // 因为s和t仅包含小写字母，共26个，因此手动建立一个hash表
        int freq[26] = { 0 };
        for(int i = 0; i < s.size(); i++)
            freq[s[i] - 'a']++;

        for(int i = 0; i < t.size(); i++) {
            freq[t[i] - 'a']--; // 此方法比较巧妙，将频次减一，然后看频次数
            if(freq[t[i] - 'a'] < 0)
                return false;
        }
        return true;
    }
};

int main() {
    cout << Solution().isAnagram("anagram", "nagaram") << endl; // true
    cout << Solution().isAnagram("rat", "car") << endl; // false
    cout << Solution().isAnagram("ab", "a") << endl;    // false
    return 0;
}
